#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/12/26 17:46
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 高级-第一个缺失的正数.py
# @Software: PyCharm
from utils.main import main, opt_list


class Solution:
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        l = len(nums)
        if l <= 0:
            return 1
        while True:
            if i >= l:
                break
            if nums[i] <= 0:
                i += 1
                continue
            x = nums[i]
            if x != i+1:
                if (x <= l) and (nums[x-1] != x):
                    nums[i], nums[x-1] = nums[x-1], nums[i]
                    continue
            i += 1
        ans = 1
        while (ans <= l) and (nums[ans-1] == ans):
            ans += 1
        return ans


def opt(nums):
    solve = Solution()
    print(nums)
    print('ans:')
    print(solve.firstMissingPositive(nums))


def opt1():
    nums = [1, 2, 0]
    opt(nums)
    print('ans=', 3)


def opt2():
    nums = [3, 4, -1, 1]
    opt(nums)
    print('ans=', 2)


def opt3():
    nums = [7, 8, 9, 11, 12]
    opt(nums)
    print('ans=', 1)


def opt4():
    nums = []
    opt(nums)
    print('ans=', 1)


def opt5():
    nums = [1, 1]
    opt(nums)
    print('ans=', 2)


if __name__ == '__main__':
    opt_list.append(opt1)
    opt_list.append(opt2)
    opt_list.append(opt3)
    opt_list.append(opt4)
    opt_list.append(opt5)
    main()
